package com.algorithm.binary;

/*
 *@Author:DOWN
 *@Date:2022/1/24 15:25
 *@Comment:二分循环 适用于 有序
 */
public class BinarySerch {

    public static <E extends Comparable<E>> int seach(E[] args, E target) {
        return seach(args, 0, args.length - 1, target);
    }

    public static <E extends Comparable<E>> int seach(E[] args, int l, int r, E target) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (args[mid].compareTo(target) == 0) {
                return mid;
            } else if (args[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 寻找大于目标值的数，并且该 数 是大于目标值的 数 中的最小一个。
     *
     * @param args   元素组
     * @param target 目标值
     * @param <E>    泛型
     * @return 返回目标索引 int
     */
    public static <E extends Comparable<E>> int upper(E[] args, E target) {
        return upper(args, 0, args.length, target);
    }

    public static <E extends Comparable<E>> int upper(E[] args, int l, int r, E target) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            //[l,r) 左闭右开 右开：大于目标值的 数 可能不存在于 该 元素组中
            //如果 mid 中间值 小于 目标值
            //则 左边界=mid+1 ， 逐步趋近 右边界
            if (args[mid].compareTo(target) <= 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public static <E extends Comparable<E>> int upperContian(E[] args, E target) {
        return upperContian(args, 0, args.length, target);
    }

    public static <E extends Comparable<E>> int upperContian(E[] args, int l, int r, E target) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (args[mid].compareTo(target) == 0) {
                return mid;
            } else if (args[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    /**
     * 查询目标值的 天花板，元素组中 包含 target 的 最 大 索引，没有 则 大于目标值 的 数。
     *
     * @param args 元素组
     * @param target 目标
     * @param <E> 泛型
     * @return int
     */
    public static <E extends Comparable<E>> int upperCeil(E[] args, E target) {
        int u = upper(args, target);
        if (u - 1 >= 0 && args[u].compareTo(target) == 0) {
            return u - 1;
        }
        return u;
    }

    /**
     * 查询目标值的 天花板，元素组中 包含 target 的 最 小 索引，没有 则 大于目标值 的 数。
     *
     * @param args 元素组
     * @param target 目标
     * @param <E> 泛型
     * @return int
     */
    public static <E extends Comparable<E>> int lowerCeil(E[] args, E target) {
        int u = upper(args, target);
        while (u - 1 >= 0 && args[u - 1].compareTo(target) == 0) {
            u = u - 1;
        }
        return u;
    }

    public static <E extends Comparable<E>> int lower(E[] args, E target) {
        return lower(args, -1, args.length - 1, target);
    }

    /**
     * 寻找小于目标值的数，并且该 数 是小于目标值的 数 中的最大一个。
     *
     * @param args   元素组
     * @param target 目标值
     * @param <E>    泛型
     * @return 返回目标索引 int
     */
    public static <E extends Comparable<E>> int lower(E[] args, int l, int r, E target) {
        while (l < r) {
            //int 类型 趋近于0时， 1+0 / 2 = 0  ， 陷入死循环 。
            int mid = l + (r - l + 1) / 2;
            if (args[mid].compareTo(target) < 0) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public static <E extends Comparable<E>> int lower_floor(E[] data, E target) {
        //因为如果整个数组中包含target元素，我们要返回的是最小索引，这个最小索引肯定紧紧挨着“小于target的最大索引”，也就是在lower结果的右侧。
        int l = lower(data, target);
        // 注意，因为我们要访问 data[l + 1]，所以，我们要先确保 l + 1 不越界，
        // 即 l + 1 < data.length
        if (l + 1 < data.length && data[l + 1].compareTo(target) == 0) {
            return l + 1;
        }
        return l;
    }

    public static <E extends Comparable<E>> int upper_floor(E[] data, E target) {
        //因为如果整个数组中包含target元素，我们要返回的是最小索引，这个最小索引肯定紧紧挨着“小于target的最大索引”，也就是在lower结果的右侧。
        int l = lower(data, target);
        // 注意，因为我们要访问 data[l + 1]，所以，我们要先确保 l + 1 不越界，
        // 即 l + 1 < data.length
        while (l + 1 < data.length && data[l + 1].compareTo(target) > 0 && data[l].compareTo(data[l + 1]) == 0) {
            return l + 1;
        }
        return l;
    }

    public static <E extends Comparable<E>> int search2(E[] data, E target) {

        // 以下代码是求解 >= target 的最小值索引
        // ----------
        int l = 0, r = data.length;

        // 在 data[l, r] 中寻找解
        while (l < r) {

            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        // ----------
        // 求解 >= target 的最小值索引算法结束
        // l 是 >= target 的最小值索引

        // 如果 data[l] == target，则返回 l；否则返回 -1
        // 注意，求解 >= target 的最小值索引，结果可能是 data.length，不是合法索引
        // 所以，我们要对 l 的合法性进行判断，即确定 l < data.length
        if (l < data.length && data[l].compareTo(target) == 0) {
            return l;
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] test = new Integer[]{88, 90, 90, 99};
        int r = lower(test, 89);
        System.out.println(r + ":" + test[r] + "");
    }
}
